/*
 * @lc app=leetcode id=70 lang=cpp
 *
 * [70] Climbing Stairs
 */
class Solution {
public:
    int climbStairs(int n) {

        if (n < 1) {
            return 0;
        }

        if (n <= 2) {
            return n;
        }

        vector<int> f(n+1, 0);
        f[1] = 1;
        f[2] = 2;

        for (int i=3; i<=n; i++) {
            f[i] = f[i-1]+f[i-2];
        }

        return f[n];
    }
};

